package com.Offer;

/*
    面试题56：数组中数字出现的次数
    一个整形数组中除了两个数字外，其他的数字都出现了两次，请找出这两个数字
    例如数组为{2,4,3,6,3,2,5,5},输出4和6
 */
public class demo56 {
    public static void main(String[] args) {
        int[] input = {2,3,3,2,3,2,5,5,6,5};
        FindNumsAppearOnce(input);
        int numberAppearingOnce = findNumberAppearingOnce(input);
        System.out.println(numberAppearingOnce);

    }

    public static void FindNumsAppearOnce(int[] data){
        if (data == null || data.length < 2)
            return ;
        int res = 0;
        for (int i = 0; i < data.length; i++) {
            res ^= data[i];
        }
        int num1 = 0;
        int num2 = 0;
        int indexOf1 = FindFirstBitIs1(res);
        for(int i = 0;i<data.length;i++){
            if(isBit1(data[i],indexOf1)){
                num1 ^= data[i];
            }else{
                num2 ^= data[i];
            }
        }
        System.out.println(num1);
        System.out.println(num2);
    }

    public static int FindFirstBitIs1(int num){
        int index = 0;
        while(num != 0){
            if((num & 1) == 1)
                break;
            num = num>>1;
            index++;
        }
        return index;
    }


    public static boolean isBit1(int number,int index){
        number = number >> index;
        return ((number&1) == 1);
    }


    /*--------------------------------------------------*/

    //举一反三：在一个数组中除了一个数出现一次外，其他数字出现了三次，找出那个数字
    //将数以二进制的形式加起来，判断每一位是否可以被三整除，不能整除的就是剩余的数的1的位置
    public static int findNumberAppearingOnce(int[] data){
        if (data == null || data.length <= 0)
            return 0;
        int[] bitSum = new int[32];
        for (int i = 0; i < data.length; i++) {
            int bitMask = 1;
            //按照二进制位数的顺序，倒着存储
            for(int j = 31;j>=0;j--){
                int bit = data[i] & bitMask;
                if(bit != 0){
                    bitSum[j] += 1;
                }
                bitMask = bitMask << 1;
            }
        }

        int res = 0;
        //关键：bitSum[32]中从0开始是所有数和的二进制的最高位，所以bitSum[31]是所有数和的最低位
        //例如{2,2,2,3,3,3,5,5,5,6}这个数组，他得到bitSum数组的最后3位是4,7,6，其他都是0
        //然后用res的右移 来按二进制的加法 添加到十进制数res上
        //例如4 7 6 第一次由于4%3 = 1，所以res为1；然后res右移，二进制为10，这时候7%3 = 1 ，所以res+=1，此时res的二进制表示为11，然后我们右移，res变为110，此时6%3 = 0 ，所以res的二进制定格在110，十进制为6，找到唯一出现一次的数
        for (int i = 0; i < bitSum.length; i++) {
            res = res << 1;
            res += bitSum[i] % 3;
        }

        return res;
    }

}
